﻿// 设置陷阱 TRAPCARD.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://algospot.com/judge/problem/read/TRAPCARD

问题
地狱炎俱乐部（Hellfire Club）是一个以强大权力自居的恶棍团体，他们的老巢被正义使者Z男子摧毁后决定离开并搬到新的地下基地。
这个新地下基地有着华丽的装饰、会议室、家庭影院、保龄球馆、内部餐厅等设施齐全，但还缺少一样东西，那就是陷阱。
无论在哪个时代和地点，恶棍们的地下基地都需要设置各种陷阱。

(a)	(b)
29.png	30.png
地狱炎俱乐部的地下基地呈现为图（a）所示的矩形形状，内部被划分为H*W个区域。每个单元格可以是走廊或房间（白色格子），也可以是被墙壁或柱子封闭的（黑色格子）。地狱炎俱乐部希望在不妨碍成员通行的情况下安装尽可能多的陷阱。俱乐部的成员对陷阱的位置非常容易记住，并且由于他们能够轻松跳过一个格子，因此通常可以避开陷阱。但是，如果在相邻的两个边上都安装了陷阱，将会导致通行不便，因此希望避免这种情况发生。图（b）展示了在（a）地图上可以放置陷阱的方式。

给定地下基地的地图，请编写一个程序来计算如何布置才能安装最多数量的陷阱。

输入
输入的第一行包含测试用例的数量C（C <= 50）。每个测试用例的第一行包含地下基地的大小H，W（1 <= H，W <= 20）。接下来的H行中，每行包含W个字符，表示地下基地的地图。字符#表示被墙壁封闭的格子，字符.表示空白格子。

输出
对于每个测试用例，首先输出可安装的最大陷阱数量，然后再输出包含陷阱位置的地下基地地图。在空白格子中安装陷阱时使用^进行标记，如果有多种安装陷阱的方法，则任意选择一种。

示例输入
2
5 3
...
#.#
#.#
#.#
...
6 10
###.###.##
.##.....#.
..#.###...
..###..##.
.####..#.#
..........
示例输出
6
^.^
#^#
#.#
#^#
^.^
19
###^###^##
.##.^.^.#^
^.#^###.^.
.^###^.##^
^####.^#^#
.^.^.^.^.^
*/
int main()
{
    std::cout << "Hello World!\n";
}

